package com.yww.algorithm.sort;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author yww
 * @description 双边快速排序，随机基准值
 * @since 2024/2/24 16:08
 */
public class QuickSortRandom {
    public static void sort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private static void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(arr, left, right); // 分区
        quick(arr, left, p - 1); // 左递归
        quick(arr, p + 1, right); // 右递归
    }

    private static int partition(int[] arr, int left, int right) {
        // 随机基准值
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(arr,idx,left); // 将基准值，交换到最左侧，按原双边逻辑
        int pv = arr[left];
        int i = left; // i 往右找 > pv
        int j = right; // j 往左找 < pv
        while (i < j) {
            while (i < j && arr[j] > pv) {
                j--;
            }
            while (i < j && arr[i] <= pv) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, i, left);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = {6, 5, 4, 3, 2, 1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }

}
